package leetcode;

/**
 * 贪心算法：加油站
 */
public class Solution31 {
    class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int curSum = 0;
            int totalSum = 0;
            int start = 0; //索引位置
            for(int i = 0; i < gas.length ; i++){
                curSum += gas[i] - cost[i];
                totalSum += + gas[i] - cost[i];

                if(curSum < 0){
                    start = i + 1;
                    curSum = 0;
                }
            }
            if(totalSum < 0){
                return -1;
            }
            return start;
        }
    }
}
